#ifndef __STRINGTRIE_HPP__
#define __STRINGTRIE_HPP__

#include <list>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cctype>

#define NUM_CHILD_PER_NODE 39 //1 + 2 + 10 + 26

static const char to_ascii[][10] = { 
  " ", "!", "c", "p", "$" , "y", "|", "$", "..", "(c)", 
  "a", "<<", "not", " ", "(r)", "-", "o", "+-", "2", "3", 
  "'", "u", "|", ".", ".", "1", "o", ">>", "1/4", "1/2", 
  "3/4", "?", "a", "a", "a", "a", "a", "a", "ae", "c", "e", 
  "e", "e", "e", "i", "i", "i", "i", "d", "ny", "o", "o",
  "o", "o", "o", "x", "0", "u", "u", "u", "u", "y", "th", 
  "ss", "a", "a", "a", "a", "a", "a", "ae", "c", "e", "e", "e", 
  "e", "i", "i", "i", "i", "d", "ny", "o", "o", "o", "o", "o", 
  "/", "0", "u", "u", "u", "u", "y", "th", "y" 
};

static bool lower_cmp(const std::string& a, const std::string& b)
{
  if (a.length() != b.length() ) 
    return false;
  for(size_t i = 0; i < a.length(); ++i)
    if (tolower(a[i]) != tolower(b[i])) 
      return false;
  return true;
}

template <class GraphNode>
class Trie {
public:
  struct ApproximateLookupItem : public std::pair<GraphNode*, std::string> {
    typedef std::pair<GraphNode*,std::string> Tbase;
    ApproximateLookupItem()
      : Tbase()
    {}
    ApproximateLookupItem(GraphNode * node, const std::string& str)
      : Tbase(node, str)
    {}
    ApproximateLookupItem(const ApproximateLookupItem &p) 
      : Tbase(p.first, p.second)
    {}
    bool operator == (const ApproximateLookupItem& o) const
    { return ((Tbase*)this)->first == o.first; }
  };

private:  
  static std::string get_ascii_str(const std::string& str)
  {
    std::string result;
    for(std::string::const_iterator c = str.begin(); c != str.end(); ++c) {
      uint16_t utf8_char = *c;
      if ( *c < 0 ) {
	utf8_char <<= 8;
	utf8_char |= 0x00FF & *(++c);
	
	if (utf8_char >= 0xC2A0 && utf8_char <= 0xC2BF )
	  result += to_ascii[utf8_char - 0xC2A0];
	else if (utf8_char >= 0xC380 && utf8_char <= 0xC3BF)
	  result += to_ascii[utf8_char - 0xC380 + 0x20];     
      } else if ( *c >= 'A' && *c <= 'Z' )
	result += tolower(*c);
      else 
	result += *c;
    }
    
    std::string result2 = "";
    for(size_t p = 0; p < result.length(); ++p)
      if ( result[p] == ' ' || result[p] == '(' || result[p] == ')' ||
	   (result[p] >= '0' && result[p] <= '9') || (result[p] >= 'a' && result[p] <= 'z') )
	{
	  result2 += result[p];
	}	 
    return result2;
  }

  static size_t edit_distance(const std::string& aa, const std::string& bb)
  {
    std::string a = aa;
    std::string b = bb;
    std::transform(a.begin(), a.end(), a.begin(), ::tolower);
    std::transform(b.begin(), b.end(), b.begin(), ::tolower);

    size_t * D1, * D2;
    assert ( (D1 = new size_t [a.length()+1]) != NULL ) ;
    assert ( (D2 = new size_t [a.length()+1]) != NULL ) ;
    
    for(size_t i = 0; i <= a.length(); ++i)
      D1[i]=i;
    
    for(size_t j = 1; j <= b.length(); ++j) {
      D2[0]=j;
      for(size_t i = 1; i <= a.length(); ++i) {
	if ( a[i-1] == b[j-1] ) D2[i] = D1[i-1];
	else D2[i] = std::min(D1[i-1], std::min(D2[i-1], D1[i])) + 1;
      }
      size_t * aux = D2;
      D2 = D1;
      D1 = aux;
    }

    size_t res = D1[a.length()];
    delete [] D1;
    delete [] D2;
    return res;
  }

  static size_t get_index(const char c)
  {
    if ( c == ' ' ) return 0;
    else if (c == '(' || c == ')') return (1 + c-'(');
    else if (c >= '0' && c <= '9') return (3 + c - '0');
    else if (c >= 'a' && c <= 'z') return (13 + c -'a');
    else assert( 0 ); 
  }

  struct TerminalNode {
    GraphNode * graph_node;
    const std::string& real_id;
    const std::string ascii_id;
    size_t curr_pos_id;
    TerminalNode(GraphNode * _node, const std::string& _rid, 
		 const std::string& _ascii, const size_t _pos_id)
      : graph_node(_node), real_id(_rid), ascii_id(_ascii), 
	curr_pos_id(_pos_id)
    { }

    bool finished_analysis(void) const 
    {
      return (curr_pos_id == ascii_id.length());
    }
    
    size_t get_new_index(void) 
    {
      assert( !finished_analysis() );
      return get_index(ascii_id[curr_pos_id++]);
    }

    ~TerminalNode() {
      //delete graph_node;
    }
    
  };

  class TrieNode {
  private:
    TrieNode** adjacents;
    std::list<TerminalNode*> terminal_main;
    std::list<TerminalNode*> terminal_akas;
    bool any_child;
   
  public:
    TrieNode()
    {
      assert((adjacents = new TrieNode* [NUM_CHILD_PER_NODE]) != NULL);
      memset(adjacents, 0x00, sizeof(TrieNode*)*NUM_CHILD_PER_NODE);
      any_child = false;
    }

    ~TrieNode() 
    {
      for(size_t adj = 0; adj < NUM_CHILD_PER_NODE; ++adj)
	if ( adjacents[adj] != NULL ) delete adjacents[adj];
      delete [] adjacents;
      typedef typename std::list<TerminalNode*>::iterator tnli;
      for(tnli it = terminal_main.begin(); it != terminal_main.end(); ++it)
	delete *it;
      for(tnli it = terminal_akas.begin(); it != terminal_akas.end(); ++it)
	delete *it;
    }
    
    void decompress (void)
    {
      if( !any_child ) {
	if ( terminal_main.size() > 0 && !terminal_main.front()->finished_analysis() ) { // unfinished main terminal
	  size_t adj = terminal_main.front()->get_new_index();
	  assert( (adjacents[adj] = new TrieNode) != NULL );
	  adjacents[adj]->terminal_main = terminal_main;
	  terminal_main.clear();	 
	  any_child = true;
	} else if ( terminal_akas.size() > 0 && !terminal_akas.front()->finished_analysis() ) { // unfinished aka terminals
	  size_t adj = terminal_akas.front()->get_new_index();
	  assert( (adjacents[adj] = new TrieNode) != NULL );
	  adjacents[adj]->terminal_akas = terminal_akas;
	  terminal_akas.clear();
	  any_child = true;
	}
      }
    }

    bool insert_main(const std::string& real_id, const std::string& key, 
		     const size_t key_pos, GraphNode* node)
    {
      if( !any_child && terminal_main.size() == 0 && terminal_akas.size() == 0 ) { // no children and no terminal nodes
	terminal_main.push_back( new TerminalNode(node, real_id, key, key_pos) );
	assert ( terminal_main.back() != NULL );
	return true;
      }

      // In case we have to decompress the terminals in this node
      decompress();
      
      if ( key_pos == key.length() ) {
	terminal_main.push_back( new TerminalNode(node, real_id, key, key_pos) );
	assert( terminal_main.back() != NULL );
	return true;
      }
      
      size_t adj = get_index(key[key_pos]);
      if ( adjacents[adj] == NULL ) {
	assert( (adjacents[adj] = new TrieNode) != NULL );
	any_child = true;
      }
    
      return adjacents[adj]->insert_main(real_id, key, key_pos+1, node);
    }

    bool insert_aka(const std::string& real_id, const std::string& key, 
		    const size_t key_pos, GraphNode* node)
    {
      if( !any_child && terminal_main.size() == 0 && terminal_akas.size() == 0 ) { 
	// no children and no terminal nodes
	terminal_akas.push_back( new TerminalNode(node, real_id, key, key_pos) );
	assert ( terminal_akas.back() != NULL );
	return true;
      }

      // In case we have to decompress the terminals in this node
      decompress();
      
      if ( key_pos == key.length() ) {
	terminal_akas.push_back( new TerminalNode(node, real_id, key, key_pos) );
	assert ( terminal_akas.back() != NULL );
	return true;
      }
      
      size_t adj = get_index(key[key_pos]);
      if ( adjacents[adj] == NULL ) {
	assert( (adjacents[adj] = new TrieNode) != NULL);
	any_child = true;
      }
    
      return adjacents[adj]->insert_aka(real_id, key, key_pos+1, node);
    }
    
    GraphNode * exact_lookup(const std::string& real_id, 
			     const std::string& key, const size_t pos) const
    {
      typedef typename std::list<TerminalNode*>::const_iterator tnl;
      if( pos == key.length() ) {
	for(tnl it = terminal_main.begin(); it != terminal_main.end(); ++it)
	  if ( lower_cmp((*it)->real_id, real_id) ) return (*it)->graph_node;
	return NULL;
      }

      size_t adj = get_index(key[pos]);
      if ( adjacents[adj] == NULL ) {
	for(tnl it = terminal_main.begin(); it != terminal_main.end(); ++it)
	  if ( lower_cmp((*it)->real_id, real_id) ) return (*it)->graph_node;
	return NULL;
      }
      
      return adjacents[adj]->exact_lookup(real_id, key, pos+1);
    }

    std::vector< ApproximateLookupItem > 
    approximate_lookup(const std::string& real_id, 
		       const std::string& key, 
		       const size_t pos, size_t remerrs, 
		       const size_t maxerrs) const
    {
      typedef typename std::list<TerminalNode*>::const_iterator tnl;
      std::vector< ApproximateLookupItem > result, tmp;
      if ( key.length() == pos ) {
	for(tnl it = terminal_main.begin(); it != terminal_main.end(); ++it)
	  if ( edit_distance( (*it)->real_id, real_id ) <= maxerrs )
	    result.push_back( ApproximateLookupItem((*it)->graph_node, (*it)->real_id) );
	for(tnl it = terminal_akas.begin(); it != terminal_akas.end(); ++it)
	  if ( edit_distance( (*it)->real_id, real_id ) <= maxerrs )
	    result.push_back( ApproximateLookupItem((*it)->graph_node, (*it)->real_id) );
	return result;
      }
      
      size_t adj = get_index(key[pos]);
      if ( remerrs == 0 ) { // no more errors are allowed
	if( adjacents[adj] == NULL )  {
	  for(tnl it = terminal_main.begin(); it != terminal_main.end(); ++it)
	    if ( edit_distance( (*it)->real_id, real_id ) <= maxerrs )
	    result.push_back( ApproximateLookupItem((*it)->graph_node, (*it)->real_id) );  
	  for(tnl it = terminal_akas.begin(); it != terminal_akas.end(); ++it)
	    if ( edit_distance( (*it)->real_id, real_id ) <= maxerrs )
	    result.push_back( ApproximateLookupItem((*it)->graph_node, (*it)->real_id) );
	  return result;
	} 
	return adjacents[adj]->approximate_lookup(real_id, key, pos+1, 0, maxerrs);
      }

      if ( !any_child ) {
	for(tnl it = terminal_main.begin(); it != terminal_main.end(); ++it)
	  if ( edit_distance( (*it)->real_id, real_id ) <= maxerrs )
	    result.push_back( ApproximateLookupItem((*it)->graph_node, (*it)->real_id) );
	for(tnl it = terminal_akas.begin(); it != terminal_akas.end(); ++it)
	  if ( edit_distance( (*it)->real_id, real_id ) <= maxerrs )
	    result.push_back( ApproximateLookupItem((*it)->graph_node, (*it)->real_id) );
	return result;
      }

    
      if ( adjacents[adj] != NULL ) {
	// no errors consumed
	result = adjacents[adj]->approximate_lookup(real_id, key, pos+1, remerrs, maxerrs);

	// insertion 1, error consumed
	tmp = adjacents[adj]->approximate_lookup(real_id, key, pos, remerrs-1, maxerrs);
	result.insert(result.end(), tmp.begin(), tmp.end());
	
	// esborrat 1, error consumed
	if (key.length() > pos+2) {
	  tmp = adjacents[adj]->approximate_lookup(real_id, key, pos+2, remerrs-1, maxerrs);
	  result.insert(result.end(), tmp.begin(), tmp.end());
	}
      } 

      for(size_t i = 0; i < NUM_CHILD_PER_NODE; ++i) {
	if ( adjacents[i] == NULL || i == adj ) continue;
	
	// substitucions, 1 error.
	tmp = adjacents[i]->approximate_lookup(real_id, key, pos+1, remerrs-1, maxerrs);
	result.insert(result.end(), tmp.begin(), tmp.end());
      }

      return result;      
    }

    static void ptabs(unsigned tabs)
    {
      for(unsigned t = 1; t <= tabs; ++t)
	std::clog << "\t";
    }
    
    void print (unsigned tabs) const {
      typedef typename std::list<TerminalNode*>::const_iterator tnl;

      for(tnl it = terminal_main.begin(); it != terminal_main.end(); ++it) {
	ptabs(tabs);
	std::clog << "Main: " << (*it)->real_id << " -- " << (*it)->ascii_id << std::endl;
      }
      for(tnl it = terminal_akas.begin(); it != terminal_akas.end(); ++it){
	ptabs(tabs);
	std::clog << "Aka: " << (*it)->real_id << " -- " << (*it)->ascii_id << std::endl;
      }
      
      for(unsigned i = 0; i < NUM_CHILD_PER_NODE; ++i)
	if (adjacents[i] != NULL) adjacents[i]->print(tabs+1); 
    }
  };

  TrieNode root;
public:
  Trie ()
  {
  }

  ~Trie()
  {
  }

  bool insert_main(const std::string& real_id, GraphNode* node) 
  {
    std::string key = get_ascii_str(real_id);
    return root.insert_main(real_id, key, 0, node);
  }

  void insert_aka(const std::string& real_id, GraphNode* node)
  {
    std::string key = get_ascii_str(real_id);
    root.insert_aka(real_id, key, 0, node);
  }

  GraphNode* exact_lookup(const std::string& real_id) const
  {
    std::string key = get_ascii_str(real_id);
    return root.exact_lookup(real_id, key, 0);
  }

  std::vector<ApproximateLookupItem> 
  approximate_lookup(const std::string& real_id, size_t maxerrs) const
  {
    std::string key = get_ascii_str(real_id);
    return root.approximate_lookup(real_id, key, 0, maxerrs, maxerrs);
  }

  void print() const
  {
    root.print(0);
  }

};

#endif
